import java.util.*;

public class Solution987 {
    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

    static class Node{
        int deep;
        int position;
        int val;

        public Node(int deep, int position, int val) {
            this.deep = deep;
            this.position = position;
            this.val = val;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<Node>> map=new HashMap<>();
        List<List<Integer>> ans=new ArrayList<>();
        dfs(root,0,map,0);
        for (int i=-1000;i<=1000;i++){
            if (map.containsKey(i)){
                List<Node> l=map.get(i);
                Collections.sort(l,(a,b)-> a.deep==b.deep?a.val-b.val:a.deep-b.deep);
                List<Integer> t=new ArrayList<>();
                for (Node node : l) {
                    t.add(node.val);
                }
                ans.add(t);
            }
        }
        return ans;
    }

    void dfs(TreeNode root,int k,Map<Integer,List<Node>> map,int deep){
        if (root==null){
            return;
        }
        List<Node> list=map.getOrDefault(k,new ArrayList<>());
        list.add(new Node(deep,k,root.val));
        map.put(k,list);
        dfs(root.left,k-1,map,deep+1);
        dfs(root.right,k+1,map,deep+1);
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(3,new TreeNode(9),new TreeNode(20,new TreeNode(15),new TreeNode(7)));
        System.out.println(new Solution987().verticalTraversal(root));
    }
}
